package SingleLinkedList;

public class SingleLinkedList implements Operations{
    public Node headNode;

    public int size;

    @Override
    public void addFirst(int data) {
        if (this.size == 0) {
            headNode = new Node(data);
            size++;
            return;
        }

         Node node = new Node(data);

        node.nextNode = this.headNode;
        this.headNode = node;
        size++;
    }

    @Override
    public void addLast(int data) {
        if (this.size == 0) {
            headNode = new Node(data);
            size++;
            return;
        }

        Node node = new Node(data);

        Node curNode = this.headNode;
        while (curNode.nextNode != null) {
            curNode = curNode.nextNode;
        }
        curNode.nextNode = node;
        size++;
    }

    @Override
    public void addIndex(int index, int data) {
        if (index < 0 || index > this.size) {
            throw new IndexException("下标不合法");
        } else if (index == 0) {
            this.addFirst(data);
        } else if (index == this.size) {
            this.addLast(data);
        } else {
            int ret = 0;
            Node curNode = headNode;
            Node node = new Node(data);
            while (ret != index - 1) {
                curNode = curNode.nextNode;
                ret++;
            }

            node.nextNode = curNode.nextNode;
            curNode.nextNode = node;
            this.size++;
        }

    }

    @Override
    public boolean contains(int key) {
        Node curNode = this.headNode;

        while (curNode != null) {
            if (curNode.val == key) {
                return true;
            }
            curNode = curNode.nextNode;
        }

        return false;
    }

    @Override
    public void remove(int key) {
        if (!this.contains(key)) {
            System.out.println("该数据不存在");
            return;
        }

        Node curNode = this.headNode;
        Node preNode = null;

        while (curNode.val != key) {
            preNode = curNode;
            curNode = curNode.nextNode;
        }

        if (preNode != null) {
            preNode.nextNode = curNode.nextNode;
            curNode = null;
        } else {
            this.headNode = this.headNode.nextNode;
        }
        this.size--;
    }

    @Override
    public void removeAllKey(int key) {

        if (!this.contains(key)) {
            System.out.println("该数据不存在");
            return;
        }

        Node curNode = this.headNode;

        int count = 0;

        while (curNode != null) {
            if (curNode.val == key) {
                count++;
            }
            curNode = curNode.nextNode;
        }

        while (count != 0) {
            this.remove(key);
            count--;
        }
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public void clear() {
        Node curNode = this.headNode;

        while (curNode != null) {
            Node next = curNode.nextNode;
            curNode.nextNode = null;
            curNode = next;
            this.size--;
        }
        this.headNode = null;
    }

    public void show() {
        Node curNode = headNode;

        while (curNode != null) {
            System.out.print(curNode.val + " ");
            curNode = curNode.nextNode;
        }
        System.out.println();
    }

//    public ListNode removeElements(ListNode head, int val) {
//        if (head == null) {
//            return null;
//        }
//
//        ListNode cur = head.next;
//        ListNode prev = head;
//
//        while (cur != null) {
//            if (cur.val == val) {
//                prev.next = cur.next;
//                cur = cur.next;
//            } else {
//                prev = cur;
//                cur = cur.next;
//            }
//        }
//
//        if (head.val == val) {
//            head = head.next;
//        }
//
//        return head;
//    }

//    public ListNode reverseList(ListNode head) {
//        if (head == null) {
//            return null;
//        }
//
//        ListNode cur = head.next;
//        head.next = null;
//
//        while (cur != null) {
//            ListNode next = cur.next;
//            cur.next = head;
//            head = cur;
//            cur = next;
//        }
//
//        return head;
//    }

//    public ListNode middleNode(ListNode head) {
//        if (head == null) {
//            return null;
//        }
//
//        ListNode fast = head;
//        ListNode slow = head;
//
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//
//        return slow;
//    }

//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//
//        if (list1 == null && list2 == null) {
//            return null;
//        } else if (list1 == null && list2 != null) {
//            return list2;
//        } else if (list1 != null && list2 == null) {
//            return list1;
//        }
//
//        ListNode cur1 = list1;
//        ListNode cur2 = list2;
//
//        ListNode head = null;
//
//        if (cur1.val <= cur2.val) {
//            head = list1;
//            cur1 = cur1.next;
//        } else {
//            head = list2;
//            cur2 = cur2.next;
//        }
//
//        ListNode cur = head;
//
//        while (cur1 != null && cur2 != null) {
//            if (cur1.val <= cur2.val) {
//                cur.next = cur1;
//                cur1 = cur1.next;
//                cur = cur.next;
//            } else {
//                cur.next = cur2;
//                cur2 = cur2.next;
//                cur = cur.next;
//            }
//        }
//
//        if (cur1 != null) {
//            cur.next = cur1;
//        }
//
//        if (cur2 != null) {
//            cur.next = cur2;
//        }
//
//        return head;
//    }

//    public ListNode partition(ListNode head, int x) {
//        // write code here
//
//        if (head == null) {
//            return null;
//        }
//
//        ListNode small = new ListNode(0);
//        ListNode large = new ListNode(0);
//        ListNode smallHead = small;
//        ListNode largeHead = large;
//        Boolean flag = false;
//
//        ListNode cur = head;
//
//        int count = 0;
//
//        while (cur != null) {
//            if (cur.val < x) {
//                small.next = cur;
//                cur = cur.next;
//                small = small.next;
//            } else if (cur.val >= x) {
//                large.next = cur;
//                cur = cur.next;
//                large = large.next;
//            }
//            // else {
//            //     if (!flag) {
//            //         ListNode next = cur.next;
//            //         cur.next = largeHead.next;
//            //         largeHead = cur;
//            //         cur = next;
//            //         flag = true;
//            //     } else {
//            //         ListNode next = cur.next;
//            //         cur.next = largeHead;
//            //         largeHead = cur;
//            //         cur = next;
//            //     }
//            // }
//        }
//
//        large.next = null;
//
//        // while (count != 0) {
//        //     ListNode node = new ListNode(x);
//        //     small.next = node;
//        //     small = small.next;
//        //     count--;
//        // }
//
//        if (!flag) {
//            small.next = largeHead.next;
//        } else {
//            small.next = largeHead;
//        }
//
//
//        return smallHead.next;
//    }

//    public boolean chkPalindrome(ListNode head) {
//        // write code here
//
//        ListNode fast = head;
//        ListNode slow = head;
//
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//
//        ListNode cur = slow.next;
//
//        ListNode node = cur;
//        ListNode last = node;
//        cur = cur.next;
//
//        while (cur != null) {
//            ListNode next = cur.next;
//            cur.next = node;
//            node = cur;
//            cur = next;
//        }
//
//        ListNode cur1 = head;
//        last.next = null;
//
//        while (node != null) {
//            if (cur1.val != node.val) {
//                return false;
//            }
//            cur1 = cur1.next;
//            node = node.next;
//        }
//
//
//        return true;
//    }

//    public int kthToLast(ListNode head, int k) {
//        //倒置，顺数第k个
//        if (head == null) {
//            return -1;
//        }
//
//        ListNode cur = head.next;
//
//        while (cur != null) {
//            ListNode next = cur.next;
//            cur.next = head;
//            head = cur;
//            cur = next;
//        }
//
//        cur = head;
//
//        while (k != 1) {
//            cur = cur.next;
//            k--;
//        }
//
//        return cur.val;
//    }

//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        int lenA = 0;
//        int lenB = 0;
//
//        ListNode curA = headA;
//        ListNode curB = headB;
//
//        while (curA != null) {
//            lenA++;
//            curA = curA.next;
//        }
//
//        while (curB != null) {
//            lenB++;
//            curB = curB.next;
//        }
//
//        int len = Math.abs(lenA - lenB);
//
//        curA = headA;
//        curB = headB;
//
//        if (lenA > lenB) {
//            while (len > 0) {
//                curA = curA.next;
//                len--;
//            }
//            while (lenB > 0) {
//                if (curA == curB) {
//                    return curA;
//                }
//                curA = curA.next;
//                curB = curB.next;
//                lenB--;
//            }
//        } else {
//            while (len > 0) {
//                curB = curB.next;
//                len--;
//            }
//            while (lenA > 0) {
//                if (curA == curB) {
//                    return curA;
//                }
//                curA = curA.next;
//                curB = curB.next;
//                lenA--;
//            }
//        }
//
//        return null;
//
//    }

//    public boolean hasCycle(ListNode head) {
//        ListNode fast = head;
//        ListNode slow = head;
//
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if (fast == slow) {
//                return true;
//            }
//        }
//
//        return false;
//    }

//    public ListNode detectCycle(ListNode head) {
//        ListNode fast = head;
//        ListNode slow = head;
//
//        while (fast != null && fast.next != null) {
//            fast = fast.next.next;
//            slow = slow.next;
//            if (fast == slow) {
//                break;
//            }
//        }
//
//        if (fast == null || fast.next == null) {
//            return null;
//        }
//
//        slow = head;
//        while (slow != fast) {
//            slow = slow.next;
//            fast = fast.next;
//        }
//
//        return slow;
//    }

}
